import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] graph = {
                {1, 1, 0, 0},
                {1, 1, 1, 0},
                {0, 1, 1, 1},
                {0, 0, 1, 1}
        };
        System.out.println(s.minMalwareSpread(graph, new int[]{0, 1}));

    }

    public int minMalwareSpread1(int[][] graph, int[] initial) {
        /**
         * 尽量减少恶意软件的传播
         * 这种直觉解法忽视了多种感染者互相连通的情况，这就会导致重复计算无效值*/
        // 1 预处理
        int n = graph.length;
        // -initial数组并不是升序，需要注意
        Arrays.sort(initial);

        // 2 遍历
        int maxCount = 0;
        int ret = initial[0];
        for(int e: initial) {
            int curCount = 0;
            for(int i = 0; i < n; i++) {
                // -仅统计横向即可
                curCount += graph[e][i];
            }
            if(curCount > maxCount) {
                ret = e;
                maxCount = curCount;
            }
        }

        // 3 返回值
        return ret;
    }

    public int minMalwareSpread(int[][] graph, int[] initial) {
        /**
         * */
        // 1 排序
        Arrays.sort(initial);

        // 2 依次去除对应元素
        int retIndex = initial[0];
        int maxCount = 1;
        // 3 根据题意进行删除，枚举出最优解
        for(int e: initial) {
            // -除了删除对应感染节点，还要切断对应连接关系，故传递e
            int curCount = minMalwareSpreadDemo(graph, splitArray(initial, e), e);
            if(curCount > maxCount) {
                retIndex = e;
                maxCount = curCount;
            }
        }

        // 4 返回值
        return retIndex;
    }

    public static int[] splitArray(int[] arr, int t) {
        /**
         * 处理数组：删除数组中的指定元素*/
        int n = arr.length;
        int[] ret = new int[n-1];
        int k = 0;
        for(int i = 0; i < n-1; i++) {
            if(arr[k] == t) {
                k ++;
            }
            ret[i] = arr[k];
            k++;
        }
        return ret;
    }

    public int minMalwareSpreadDemo(int[][] graph, int[] initial, int skip) {
        /**
         * 尽量减少恶意软件的传播
         * 计算连通量*/
        // 1 初始化
        int n = graph.length;
        Arrays.sort(initial);
        initialize(n, initial);

        // 2 合并连通量
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                if(i == skip || j == skip) {
                    continue;
                }
                if(graph[i][j] == 1) {
                    union(i, j);
                }
            }
        }

        // 3 统计未被感染地节点数量并返回
        int count = 0;
        for(int i = 0; i < n; i++) {
            if(!virus[find(i)]) {
                count ++;
            }
        }
        return count;
    }

    // 创建并查集
    public static int MAX_N;
    public static int[] father;
    public static int[] size;
    public static int[] stack;
    // -标记集合是否有病毒，及病毒的数量
    public static boolean[] virus;
    public static int[] theNumberOfVirus;

    public static void initialize(int n, int[] initial) {
        /**
         * 并查集初始化*/
        MAX_N = n;
        father = new int[MAX_N];
        size = new int[MAX_N];
        stack = new int[MAX_N];
        virus = new boolean[MAX_N];
        theNumberOfVirus = new int[MAX_N];
        for(int i = 0; i < n; i++) {
            father[i] = i;
            size[i] = 1;
        }
        // -初始化病毒
        for(int e: initial) {
            virus[e] = true;
            theNumberOfVirus[e] = 1;
        }
    }

    public static int find(int a) {
        /**
         * 找到a元素所在集合的代表元素-扁平化*/
        int i = 0;
        while(a != father[a]) {
            stack[i++] = a;
            a = father[a];
        }
        while(i > 0) {
            father[stack[--i]] = a;
        }
        return a;
    }

    public static boolean isSameSet(int a, int b) {
        /**
         * 判断a、b元素是否处于同一集合中*/
        return find(a) == find(b);
    }

    public static void union(int a, int b) {
        /**
         * 合并a、b元素所在集合-小挂大*/
        int fa = find(a);
        int fb = find(b);
        if(fa != fb) {
            if(size[fa] >= size[fb]) {
                // -计算集合元素个数
                size[fa] += size[fb];
                // -a、b集合合并，有一个感染则全感染
                virus[fa] = virus[fa] || virus[fb];
                // -若是b存在病毒，则累加至a
                if(theNumberOfVirus[fb] > 0) {
                    theNumberOfVirus[fa] += theNumberOfVirus[fb];
                }
                // -小挂大
                father[fb] = fa;
            } else {
                size[fb] += size[fa];
                // -a、b集合合并，有一个感染则全感染
                virus[fb] = virus[fa] || virus[fb];
                // -若是b存在病毒，则累加至a
                if(theNumberOfVirus[fa] > 0) {
                    theNumberOfVirus[fb] += theNumberOfVirus[fa];
                }
                father[fa] = fb;
            }
        }
    }
}
